COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\\M1BASL30\M2BASB30
C00021 00003
C00026 ENDMK
C⊗;
\\M1BASL30;\M2BASB30;
\C\F2Background: An Overview of LISP Portability Issues

\F1
\J


The critical task in this project is the specification, implementation, 
and instrumentation of professional production-quality 
portable LISP.
This is 
no small undertaking; though several projects have addressed
selected parts of this problem, no one has successfully
handled this general problem in a comprehensive LISP system.

This initial section discusses the current state of LISP technology and
motivates some of the reasons for our conclusions. Those
conclusions are drawn 
 in the sections entitled "Constraints", "Recommendations", and
"Budget"; thus this section need be read only by the morbidly curious.

To begin, the LISP dialect that this
project supports must be a "professional-quality" LISP, meaning that
language issues related to the application of LISP as a general-purpose language
must be addressed and solved; 
the language cannot be a "toy" LISP.  There are only two
LISP families that begin to 
meet this specification: InterLISP and MacLISP.

Unfortunately, one cannot make a simple decision: "we will support InterLISP" or
"we will support MacLISP" because a great percentage of programs in these dialects
have implementation-dependent characteristics. These dependencies
include 
anacronisms of the operating system, 
the underlying machine, and specific input/output
devices.
These
dependencies should be isolated and not  proliferated unnecessarily
into the next
generation of LISP implementations. More subtly, these dependencies include
historical deficiencies --language usages, that in light of current knowledge,
are non-optimal.
 Therefore we must delimit the
set of programs that will be considered "portable".
This delimiting process has an interesting  and  attractive aspect:
potentially, one should be able to  delimit a Kernel LISP (KLISP)
that subsets both InterLISP and MacLISP in the sense that one can
prescribe subsets of these languages that are semi-automatically translatable
to KLISP. Such a translation process  can be supported by an intelligent version
of a TRANSOR-like program. For example, this 
translator can perhaps perform interactively like the SPELL
program, using dictionaries and exception dictionaries of transformations
integrated within an interactive display system.

Those segments of code that are machine/dialect dependent can be handled by 
using "personality modules". Such modules are also attractive for implementing
incremental language enhancements; each "attached data-structure processor"
would implement a particular abstract data structure: a floating-point pack
would include necessary components to read, evaluate, print, 
manage storage, and do arithmetic
on floating point objects; similar packages would exist for strings, windows,
and dialect-dependent language constructs.

The specification of such a KLISP is a non-trivial task, similar in scope to 
defining an "ANSI standard LISP"; it should be done however. Furthermore, it
is a non-trivial 
problem to implement such a KLISP that contains sufficient extensibility
to gracefully interface to the personality modules and data structure packages.
However, the benefits of such an approach are appreciable; one can expect
a large amount of both InterLISP and MacLISP code to become readily accessible.
Furthermore, the specification and implementation of the virtual machine for  
KLISP becomes more crisp since the dialect-dependent features become the
province of the outboard processors.

Notice that we have now replaced the original problem with two, hopefully
more tractable, problems: the specification of a LISP subset --KLISP, and
the specification and implementation of a virtual machine --VM-- 
that will make this KLISP portable. First, let us address the problem of
an acceptable  KLISP.

What has been done? Unfortunately very little in general, but a few rays of 
hope in specific areas.
A LISP group  at Utah has defined a LISP subset called Standard
LISP.
The major problem with this work is the 
scope of the LISP. Since Standard LISP is
viewed as the implementation vehicle for the algebraic
manipulation system, REDUCE, rather than a general production
LISP environment, many LISP features have been ignored. A notable
lacking  is their weak treatment of functional objects. Given the increased
importance of such data structures, the  exclusion is a serious one.

One of the major dialects in Europe is VLISP  --the "V" standing for Vincennes.
The project contains some  interesting theoretical and
practical components, including careful attention to tail recursion 
optimization in both the interpreter and the  compiler.
Though VLISP is viewed as a general purpose LISP tool,
unfortunately many of the objections to Standard LISP can be  leveled at
VLISP, including the treatment of functional objects.
Standard LISP and VLISP projects similar in scope, though different in 
motivation; we will return to these projects again when discussing virtual
machines.

It appears that the MacLISP community  has a reasonable handle on the
cross dialect problem, having
to convert between NIL, MacLISP and LISP-machine LISP.
The MIT people are doing a conscientious job of maintaining "controlled
incompatibility" between these three LISPs.
For example, as new features are developed for NIL or LM LISP, they are
retrofitted to MacLISP if possible; furthermore, features like EVAL-WHEN,
 IF-FOR-MACLISP, and IF-FOR-LISPM help control the incompatibilities.
Unfortunately, all of these MacLISP efforts are targeted to quite
different machines and  there is no sense of a Virtual MacLISP Machine.

The InterLISP community has finessed the problem of dialects rather
effectively: there is one InterLISP. 
As we have discussed above, we would rather address the dialect problem
directly; thus the MIT experience can be quite valuable.
However, the InterLISP community has a reasonable handle on the
problem of porting a large LISP system.
Their experience with AltoLISP, and InterLISP-D represent some
of the finest work in developing portable systems. This includes
retargeting and measurement of the resulting product. It is a truly
professional piece of work. 

The major difficulties in establishing a KLISP involve a minority of the
language constructs of LISP dialects; we believe
that there is a serious kernel of LISP
that is mechanically comparable between dialects.
A short catalog of troublesome spots follows: InterLISP  features that
must be dealt with include
spaghetti stacks, JSYS usage (page mapping, general input and output,
function/simple value dichotomy and its support,
static/dynamic variable selection. In MacLISP derivatives we will 
have to ponder stack groups, closures, packages, and again
i/o (windows readtables, etc), function/simple values, and
static/dynamic scoping conventions.
Surely there are other spots awaiting the unwary, and concerted effort will
expose them. The LISP Standards group will be pursuing these goals; I expect to
take part in some of these discussions.



Given that one can isolate an effective KLISP, then the issues of defining
and implementing a Virtual Machine appears: what is its "architecture"?
what input/output is considered "primitive"?
how is it implemented? 
how do we measure its performance?
These are all non-trivial problems, but at least now we have a well-defined 
base-point established. In fact, technology is much more encouraging in the
domain of Virtual Machine definition and implementation.

The most carefully documented work on virtual LISP machines has been
done by Xerox PARC on InterLISP. Most of that work has been cleared by Xerox
and their personnel is quite willing to discuss their work.
The earliest work was done by Peter Deutsch and colleagues, moving InterLISP-10
to the Alto. This effort involved designing, implementing, and measuring 
a VM for InterLISP. It took about six man-months to specify the first cut
of the VM; then a team of between three and five people spent about eighteen 
months implementing the VM; and finally another eighteen months was spent 
tuning the implementation.
Dove-tailed into the Alto effort, Xerox began the transportation of Interlisp
onto the Dorado; again, that effort took three-to-five people about three
years to implement a high-performance VM. Work is continuing at Xerox, refining 
the implementation.
At least two further efforts are underway: BBN is implementing the VM on their
Jericho processor --approximately a CADR-class machine, and a team at USC-ISI
is implementing the VM on a VAX. Little data is available yet on these efforts.

The european VLISP has 
has been available on a wide class of machines
ranging from the Intel 8080 to the PDP-10. Though
these implemenatations have been hand coded, recent work has established 
the basis for portable implementations based on 
 a virtual machine called
the "VCMC2".
The main drawbacks in this effort involve 
the current depth of development: 
 simple
input/output and storage management considerations, 
resulting in poor data types and weak functional objects.
The foundations are strong and the approach is well worth consideration;
as the technology matures these difficulties may be addressed.

In an effort similar in scope to that of VLISP, the Standard LISP group at
Utah has defined and implemented a portable LISP system based on a "P-code"
machine. The problems here are similar to those of  VLISP: a weakend LISP
leading to a weak implementations strategy. Currently, the portability
technology of Standard LISP is superior to that of VLISP --somewhat
bemusing since VLISP represents a potentially more general "strain" of LISP.

Besides the already mentioned InterLISP work, the other major portability effort
for production quality LISP is that of MIT's NIL project. This effort springs from
the MacLISP school and is driving for a "third-generation" MacLISP for the large
address-space machines. The initial target is the VAX, with  the MC68000 
and other machines in mind; for example,
remarks have been made about the possibility of  defining  a VM on CADR so that
NIL would run there. 
Unfortunately, the problems of virtual
architecture have taken a back-seat to  the realities of getting NIL running on 
the VAX, though they do  expect to address the question in the future.
Adding a VM to an existing  implementation is a tricky business, as the InterLISP
experience has shown.

Of course, one should consider the macro machine of the CADR  as a virtual machine
for LISP. The major difficulty here is that, though a compiler from LISP
machine LISP
to the macro-level machine exists, 
a great deal of LISP code has been moved into the
micro kernel; this  makes portability more difficult. 
To effectively make the macro-machine  a virtual
architecture one would have to remove this LISP code, and sanitize the
marco/micro interface.

Finally, we mention a possible, but more speculative candidate: Scheme.
Scheme may offer a reasonable approximation to a 
KLISP and also its internal Scheme Chip representation may represent a viable 
VM. 

So to summarize, we have a strong collection of competitors for both the
KLISP and for the representation of the VM. Unfortunately no one
candidate stands out as vastly superior to its contemporaries. A major
part of our work will involve the delimiting and defining of the KLISP and
the VM.

The task is a major one: to pull together and unify a basis for the language
and specify an effective virtual architecture for that language.
\.





\C\F2Constraints\F1
\J
These chaotic conditions must now be  reconciled with a well-defined, concise
set of constraints: the proposed LISP must be 
immediately specified, economically 
implemented, of production-quality, and portable --at least implementable
on the DEC PDP-10 and the LISP machine in the very near future.

These conditions crystalize the chaos almost immediately. The combination of
immediacy,
economics, and production-quality implies that the dialect be extant. One cannot
realistically engage in design experiments when a product that
must satisfy professional LISP personnel is expected in minimal time.
Furthermore, the cost constraint drives portability; one cannot indulge 
deeply in research-related ventures of virtual architectures when the product is to
be developed with mininal cost.

Therefore one must look at the existing technology, not future
promises: what  LISP dialect
currently exists, supports portability, and is accepted by
a large segment of the LISP community as a production-quality
 system?  InterLISP.
\.





\C\F2Recommendation\F1
\J
\F21.\F1 Immediately begin to 
delimit a subset of InterLISP and MacLISP that will
allow programming to continue independent of the final target dialect.
This subset will be defined such that at most a simple TRANSOR operation  is 
required to transform the program between dialects.

\F22.\F1 Port InterLISP to the LISP machine, building on the extensive base of
experience at Xerox PARC, refining the user interface to exploit the
LISP machine's elegant display system. The results of this project should be of
great interest to LMI; we should expect their cooperation.

A minimum of tools need be developed to support the growth of the kernel since
many of the necessities are already in place, supporting  LISP machine LISP.

\F23.\F1 In parallel with this effort, begin to extract a kernel KLISP
that will 
support both MacLISP and InterLISP derivatives in the future.
This kernel will be based on experience with our first recommendation.
As experience is gained, more complex TRANSOR-like programs will be  developed.

\F24.\F1 Simultaneously, investigate the 
possibilities of lifting the InterLISP VM to a higher
 level of portability. Porting large
LISP systems is currently at best an art; that
situation must improve. 
The experience of the Standard LISP and VLISP groups will be helpful
here. More generally, compiler technology like that of the CMU PQCC may
be applicable.

This set of recommendations represents the "low road" to a KLISP. The experience
gained in comparing the implementation effort of InterLISP on the LISP machine
versus LISP machine LISP  on that same machine will aid immeasurably
in the definition and implementation of both KLISP and VM.
\.

\C\F2Budget\F1
\;three technical people plus one business type: two years

five staff members

LISP machine

lots of dec 10 time 
\.